#include"stack.h"
void Sweap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}


int GetMidIndex(int *a,int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
            return mid;
        else if (a[right] > a[left])
            return left;
        else
            return right;
    }
    else //a[left]<a[mid]
    {
        if (a[mid] < a[right])
            return mid;
        else if (a[right] < a[left])
            return left;
        else
            return right;
    }
}

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    int mid = GetMidIndex(a, left, right);
    Sweap(&a[left], &a[mid]);
    
    int keyi = left;
    while (left < right)
    {
        while (left < right && a[right] >= a[keyi])
        {
            right--;
        }
        while (left < right && a[left] <= a[keyi])
        {
            left++;
        }
        Sweap(&a[left], &a[right]);
    }
    Sweap(&a[keyi], &a[left]);
    keyi = left;
    return keyi;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int mid = GetMidIndex(a, left, right);
    Sweap(&a[left], &a[mid]);
    int key=a[left];
    int hole = left;
    while (left < right)
    {
        while (left < right && a[right] >= key)
        {
            right--;
        }
        a[hole] = a[right];
        hole = right;

        while (left < right && a[left] <= key)
        {
            left++;
        }
        a[hole] = a[left];
        hole = left;
    }
    a[hole] = key;
    return hole;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    int mid = GetMidIndex(a, left, right);
    Sweap(&a[left], &a[mid]);
    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi]&&++prev!=cur)
        {
            Sweap(&a[cur], &a[prev]);
        }
        ++cur;
    }
    Sweap(&a[keyi], &a[prev]);
    keyi = prev;
    return keyi;
}

void QuickSortNonR(int* a, int left, int right)
{
    Stack st;
    StackInit(&st);
    StackPush(&st,right);
    StackPush(&st,left);
    while (!IsEmpty(&st))
    {
        int begin = StackTop(&st);
        StackPop(&st);

        int end = StackTop(&st);
        StackPop(&st);

        int keyi = PartSort3(a, begin, end);
        if (keyi + 1 < end)
        {
            StackPush(&st, end);
            StackPush(&st, keyi+1);

        }

        if (keyi -1>begin)
        {
            StackPush(&st, keyi-1);
            StackPush(&st, begin);

        }
    }
    StackDestroy(&st);

}

void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;

    int keyi = PartSort2(a, left, right);
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);

}
